﻿using System;
using System.Collections.Generic;
using System.Text;

namespace ValidParentheses
{
    public class Solution
    {
        public bool IsValid(string s)
        {
            if (string.IsNullOrWhiteSpace(s))
            {
                return true;
            }

            Stack<char> stack = new Stack<char>();
            foreach (var c in s)
            {
                if (c == '(' || c == '[' || c == '{')
                {
                    stack.Push(c);
                    continue;
                }

                if (stack.Count == 0)
                {
                    return false;
                }

                if (c == ')' && stack.Peek() != '(')
                {
                    return false;
                }
                else if (c == ']' && stack.Peek() != '[')
                {
                    return false;
                }
                else if (c == '}' && stack.Peek() != '{')
                {
                    return false;
                }

                stack.Pop();
            }

            return stack.Count == 0;
        }
    }

    //// 效率更高些
    //public class Solution
    //{
    //    public bool IsValid(string s)
    //    {
    //        if (string.IsNullOrWhiteSpace(s))
    //        {
    //            return true;
    //        }
    //        var brackets = new Dictionary<char, char>() { { ')', '(' }, { ']', '[' }, { '}', '{' } };
    //        Stack<char> stack = new Stack<char>();
    //        foreach (var c in s)
    //        {
    //            if (brackets.ContainsValue(c))
    //            {
    //                stack.Push(c);
    //            }
    //            else if (brackets.ContainsKey(c))
    //            {
    //                if (stack.Count == 0 || stack.Peek() != brackets[c])
    //                {
    //                    return false;
    //                }
    //                stack.Pop();
    //            }
    //        }
    //        return stack.Count == 0;
    //    }
    //}
}
